package com.wcj.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 给你两个正整数 n 和 k 。
 *
 * 如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。
 *
 * 考虑整数 n 的所有因子，将它们 升序排列 。请你返回第 k 个因子。
 * 如果 n 的因子数少于 k ，请你返回 -1 。
 */
public class n的第k个因子 {
    public static void main(String[] args) {
        System.out.println(kthFactor(12,5));
    }


    public static int kthFactor(int n, int k) {
        Set<Integer> sortSet = new TreeSet<Integer>((o1, o2) -> o1 - o2);
        sortSet.add(1);
        sortSet.add(n);
        for (int i = 2; i < n; i++){
            if (n % i == 0){
                sortSet.add(i);
            }
        }
        int index = 1;
        for (Integer integer : sortSet) {
            if (index == k){
                return integer;
            }
            index++;
        }
        return -1;
    }

    public static int kthFactor2(int n, int k) {
        List<Integer> param = new ArrayList<>();
        param.add(1);
        param.add(n);
        for (int i = 2; i < n; i++){
            if (n % i == 0){
                param.add(i);
            }
        }
        param.sort((o1, o2) -> o1 - o2);
        return param.size() >= k ? param.get(k - 1):-1;
    }

    /**
     * 效率最高
     * @param n
     * @param k
     * @return
     */
    public static int kthFactor3(int n, int k) {
        if (k == 1){
            return 1;
        }
        int index = 1;
        for (int i = 2; i <= n; i++){
            if (n % i == 0){
                index++;
                if (index == k){
                    return i;
                }
            }
        }
        return -1;
    }
}
